1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits, and more specifically to a method of generating an optimized placement of cells for an integrated circuit chip using energetic placement with alternating contraction and expansion operations.
2. Description of the Related Art
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process ha, increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield. The arrangement of individual cells in an integrated circuit chip is known as a cell placement.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Prior art methods for achieving this goal comprise generating one or more initial placements, modifying the placements using optimization methodologies including force directed placement or simulated annealing, constructive placement, or Genetic Algorithms such as simulated evolution, and comparing the resulting placements using a cost criteria.
The field of optimization is very old. Simple mathematical optimizations have been performed since antiquity. Newton and Leibnitz's invention of calculus provided a breakthrough in the tools available, and following developments such as the calculus of variations, statistical optimization, and programming methods (linear and integer) have produced optimization techniques that are very effective for a significant class of problems.
Typically, an optimization problem involves a system whose configuration is specified by a set of numbers. There is a "cost" function that can be evaluated for any given set of values for the numbers; the "optimum" configuration is that which has the minimum cost over all possible assignments of values to the set of numbers. Usually, the set of numbers is a finite set, but an important class of optimization problems involves an infinite set of numbers.
A problem like the famous Traveling Salesman Problem (What is the best route to visit a given set of cities to minimize travel time?) involves a finite set of numbers (list the city numbers in the order they are to be visited), while an optimal-trajectory problem (What is the best way to fly an airplane to a given altitude above a sea-level takeoff so that fuel consumption is minimized?) involves an infinite set of numbers (there are an infinite number of points in a continuous trajectory function).
Unfortunately, a large class of optimization problems belong to what is known as the NP-complete class of problems; i.e., problems whose solutions cannot be found in polynomial time by algorithms implemented on modern computers. These optimization problems are usually solved "heuristically", i.e., with algorithms that search as wide a range of feasible configurations as possible, evaluate a function giving a configuration's cost, and hope to "visit" a configuration with a very low cost, i.e., a near-optimal solution.
Clever algorithms have been devised that perform "directed searches", i.e., searches that do not waste time examining configurations known in advance to have suboptimal cost values.
A placement methodology exists in the art that is generally known as "force directed placement". In this method, interconnected cells are represented as masses that exert attractive forces on each other, where the attractive forces are proportional to the distances between the cells. If the cells are allowed to move freely, each cell moves in the direction of the resultant force on it until the system achieves equilibrium.
If all of the cells in the network are allowed to move freely, the system will achieve equilibrium when all the interconnected cells occupy the same location, i.e., they are on top of each other. Since such a placement is physically unfeasible, several different methods have been tried to prevent this "collapse."
In most practical designs, fixed cells or pads at the periphery of the placement area "pull" the inner movable cells apart, so that a feasible placement is achieved. In other formulations, "repulsive" forces between the elements prevent collapse.
Although effective to a limited extent, these prior art methods encounter difficulties in producing effective placements for extremely large integrated circuit chips containing hundreds of thousands or even millions or more cells. A need exists for a placement methodology that provides this capability, especially in view of continuous advancements in fabrication technology that enable such large numbers of cells to be formed on a single chip.